package 回溯.不熟;

import java.util.ArrayList;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 复原ip地址93.java
 * @createTime 2023年01月07日 14:05:00
 */
public class 复原ip地址93 {
	List<String> result = new ArrayList<>();

	public List<String> restoreIpAddresses(String s) {
		backTrace(s, 0, 0);
		return result;
	}

	StringBuilder sb = new StringBuilder();

	public void backTrace(String s, int curIndex, int ipSplitNum) {
		//如果到了最后，则加入
		if (s.length() == curIndex && ipSplitNum == 4) {
			result.add(sb.toString());
			return;
		}
		//满足其中一个条件
		if (curIndex == s.length() || ipSplitNum == 4) {
			return;
		}
		//截取一段,然后判断这一段是否合法，如果合法则作为一段
		for (int i = curIndex; i < s.length(); i++) {
			String str = s.substring(curIndex, i + 1);
			//合法性校验
			if (!isValid(str)) {
				continue;
			}
			sb.append(str);
			if (ipSplitNum < 3) {
				sb.append(".");
			}
			backTrace(s, i + 1, ipSplitNum + 1);
			sb.delete(curIndex + ipSplitNum, i + ipSplitNum + 2);
		}
	}

	public boolean isValid(String str) {
		//字符串大于1位时候，第一位不能是0
		if (str.length() > 1 && str.charAt(0) == '0') {
			return false;
		}
		int nums = 0;
		for (int i = 0; i < str.length(); i++) {
			//字符的合法性校验
			if (str.charAt(i) > '9' || str.charAt(i) < '0') {
				return false;
			}
			//字符串需要在0~255之间
			nums = nums * 10 + (str.charAt(i) - '0');
			if (nums > 255) {
				return false;
			}
		}
		return true;
	}
}
